/*
   This file is part of Fjalar, a dynamic analysis framework for C/C++
   programs.

   Copyright (C) 2007-2018 University of Washington Computer Science & Engineering Department,
   Programming Languages and Software Engineering Group

   Copyright (C) 2004-2006 Philip Guo (pgbovine@alum.mit.edu),
   Copyright (C) 2008-2009 Robert Rudd (rudd@csail.mit.edu),
   MIT CSAIL Program Analysis Group

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.
*/

/* fjalar_main.c:

   This file contains most of the code to interact with the Valgrind
   core.  It is called from mc_main.c since mc_main.c is the
   launching-point for Fjalar.
*/

#include "my_libc.h"


#include "pub_tool_basics.h"
#include "pub_tool_aspacemgr.h"
#include "pub_tool_hashtable.h"     // For mc_include.h
#include "pub_tool_xarray.h" //for clientstate
#include "pub_tool_options.h"
#include "pub_tool_libcbase.h"
#include "pub_tool_libcassert.h"
#include "pub_tool_libcprint.h"
#include "pub_tool_machine.h"
#include "pub_tool_mallocfree.h"
#include "pub_tool_oset.h"
#include "pub_tool_replacemalloc.h"
#include "pub_tool_stacktrace.h"
#include "pub_tool_clientstate.h"

#include "generate_fjalar_entries.h"
#include "fjalar_main.h"
#include "fjalar_runtime.h"
#include "fjalar_tool.h"
#include "fjalar_select.h"
#include "disambig.h"
#include "mc_include.h"
#include "typedata.h"
#include "vex_common.h"
#include "kvasir/kvasir_main.h"
#include "kvasir/dyncomp_main.h"

// Global variables that are set by command-line options
Bool fjalar_debug = False;
Bool fjalar_debug_dump = False;
Bool fjalar_print_dwarf = False;
Bool fjalar_print_IR = False;
Bool fjalar_with_gdb = False;
Bool fjalar_ignore_constants = False;
Bool fjalar_merge_constants = False;
Bool fjalar_ignore_globals = False;
Bool fjalar_dump_globals = False;
Bool fjalar_ignore_static_vars = False;
Bool fjalar_all_static_vars = False;
Bool fjalar_default_disambig = False;
Bool fjalar_smart_disambig = False;
Bool fjalar_output_struct_vars = False;
Bool fjalar_flatten_arrays = False;
Bool fjalar_func_disambig_ptrs = False;
Bool fjalar_disambig_ptrs = False;
int  fjalar_array_length_limit = -1;

// adjustable via the --struct-depth=N option:
UInt fjalar_max_visit_struct_depth = 4;
// adjustable via the --nesting-depth=N option:
UInt fjalar_max_visit_nesting_depth = 2;

// These are used as both strings and boolean flags -
// They are initialized to 0 upon initiation so if they are
// never filled with values by the respective command-line
// options, then they can be treated as False
const HChar* fjalar_dump_prog_pt_names_filename = 0;
const HChar* fjalar_dump_var_names_filename = 0;
const HChar* fjalar_trace_prog_pts_filename = 0;
const HChar* fjalar_trace_vars_filename = 0;
const HChar* fjalar_disambig_filename = 0;
const HChar* fjalar_xml_output_filename = 0;

// Are we printing decls because we are debugging?
Bool doing_debug_print = False;

// The filename of the target executable:
const HChar* executable_filename = 0;

// Mapping between Dwarf Register numbers and
// valgrind function to return the value
// Below comment is ripped from GCC 4.3.1

/* Define the register numbers to be used in Dwarf debugging information.
   The SVR4 reference port C compiler uses the following register numbers
   in its Dwarf output code:
	0 for %eax (gcc regno = 0)
	1 for %ecx (gcc regno = 2)
	2 for %edx (gcc regno = 1)
	3 for %ebx (gcc regno = 3)
	4 for %esp (gcc regno = 7)
	5 for %ebp (gcc regno = 6)
	6 for %esi (gcc regno = 4)
	7 for %edi (gcc regno = 5)
   The following three DWARF register numbers are never generated by
   the SVR4 C compiler or by the GNU compilers, but SDB on x86/svr4
   believes these numbers have these meanings.
	8  for %eip    (no gcc equivalent)
	9  for %eflags (gcc regno = 17)
	10 for %trapno (no gcc equivalent)

*/

#if defined(VGA_amd64)
// AMD64 Dwarf to Architecture mapping is (thankfully) specified
// in the AMD64 ABI (http://x86-64.org/documentation/abi.pdf)
Addr (*get_reg[16])( ThreadId tid ) = {
  VG_(get_xAX),
  VG_(get_xDX),
  VG_(get_xCX),
  VG_(get_xBX),
  VG_(get_xSI),
  VG_(get_xDI),
  VG_(get_FP),
  VG_(get_SP),
  VG_(get_R8),
  VG_(get_R9),
  VG_(get_R10),
  VG_(get_R11),
  VG_(get_R12),
  VG_(get_R13),
  VG_(get_R14),
  VG_(get_R15),
};
#else
Addr (*get_reg[11])( ThreadId tid ) = {
  VG_(get_xAX),
  VG_(get_xCX),
  VG_(get_xDX),
  VG_(get_xBX),
  VG_(get_SP),
  VG_(get_FP),
  VG_(get_xSI),
  VG_(get_xDI),
  VG_(get_IP),
  NULL,
  NULL
};
#endif

// For debugging purposes, a mapping between
// DWARF location atoms and their string
// representation
const HChar* dwarf_reg_string[9] = {
  "xAX",
  "xCX",
  "xDX",
  "xBX",
  "xSP",
  "xFP",
  "xSI",
  "xDI",
  "xIP"
};

// located in VEX/priv/main_util.c
extern void vex_bzero(void* s, UInt n);
// located in my_libc.c
extern void setNOBUF(FILE *stream);

/*------------------------------------------------------------*/
/*--- Entry and Exit Handling                              ---*/
/*------------------------------------------------------------*/

// (comment added 2005)  
// TODO: We cannot sub-class FunctionExecutionState unless we make
// this into an array of pointers. Have one stack for
// each thread. We'll be wasteful and just have the maximum number
// of threads.
FunctionExecutionStateStack1d *FunctionExecutionStateStack;


// The first free slot in FunctionExecutionStateStack
// right above the top element:
int *fn_stack_first_free_index;

// The top element of the stack is:
// FunctionExecutionStateStack[fn_stack_first_free_index - 1]

typedef VG_REGPARM(1) void entry_func(FunctionEntry *);

// This inserts an IR Statement responsible for calling func
// code before the instruction at addr is executed. This is primarily
// used for inserting the call to enter_function on function entry.
// It is also used for handling of 'function priming' for GCC 3 (see
// comment above prime_function). The result of looking up addr in
// table will be passed to func as it's only argument. This function
// does nothing if it is unable to successfully look up addr in the
// provided table.
static void handle_possible_entry_func(MCEnv *mce, Addr64 addr,
				       struct genhashtable *table,
				       const char *func_name,
				       entry_func func) {
  IRDirty  *di;
  FunctionEntry *entry = gengettable(table, (void *)(Addr)addr);

  if(!entry) {
      return;
  }

  // If fjalar_trace_prog_pts_filename is on (we are using a ppt list
  // file), then DO NOT generate IR code to call helper functions for
  // functions whose name is NOT located in prog_pts_tree. It's faster
  // to filter them out at translation-time instead of run-time
  if (entry && (!fjalar_trace_prog_pts_filename ||
		prog_pts_tree_entry_found(entry))) {
    UWord entry_w = (UWord)entry;
    di = unsafeIRDirty_0_N(1/*regparms*/, func_name, func,
			 mkIRExprVec_1(IRExpr_Const(IRConst_UWord(entry_w))));

    // For function entry, we are interested in observing the stack
    // and frame pointers so make sure that they're updated by setting
    // the proper annotations:

    entry->entryPC = addr;

    FJALAR_DPRINTF("Found a valid entry point at %x for\n", (UInt)addr);

    // We need all general purpose registers.
    di->nFxState = 9;
    vex_bzero(&di->fxState, sizeof(di->fxState));

    di->fxState[0].fx     = Ifx_Read;
    di->fxState[0].offset = mce->layout->offset_SP;
    di->fxState[0].size   = mce->layout->sizeof_SP;
    di->fxState[1].fx     = Ifx_Read;
    di->fxState[1].offset = mce->layout->offset_FP;
    di->fxState[1].size   = mce->layout->sizeof_FP;
    di->fxState[2].fx     = Ifx_Read;
    di->fxState[2].offset = mce->layout->offset_IP;
    di->fxState[2].size   = mce->layout->sizeof_IP;

    di->fxState[3].fx     = Ifx_Read;
    di->fxState[3].offset = mce->layout->offset_xAX;
    di->fxState[3].size   = mce->layout->sizeof_xAX;
    di->fxState[4].fx     = Ifx_Read;
    di->fxState[4].offset = mce->layout->offset_xBX;
    di->fxState[4].size   = mce->layout->sizeof_xBX;
    di->fxState[5].fx     = Ifx_Read;
    di->fxState[5].offset = mce->layout->offset_xCX;
    di->fxState[5].size   = mce->layout->sizeof_xCX;

    di->fxState[6].fx     = Ifx_Read;
    di->fxState[6].offset = mce->layout->offset_xDX;
    di->fxState[6].size   = mce->layout->sizeof_xDX;
    di->fxState[7].fx     = Ifx_Read;
    di->fxState[7].offset = mce->layout->offset_xSI;
    di->fxState[7].size   = mce->layout->sizeof_xSI;
    di->fxState[8].fx     = Ifx_Read;
    di->fxState[8].offset = mce->layout->offset_xDI;
    di->fxState[8].size   = mce->layout->sizeof_xDI;

    stmt('V',  mce, IRStmt_Dirty(di) );
  }
}

// This gets updated whenever we encounter a Ist_IMark instruction.
// It is required to track function exits because the address does not
// come with the Ist_Exit IR instruction:
static Addr currentAddr = 0;

// This hash table simply ensures do not calculate the entry point for
// a function multiple times. Due to the way entry is handled, the
// handle_possble_entry function is called once for every instruction
// in the original program. We should only calculate the entry point
// once at the first instruction of the function.
static struct  genhashtable *funcs_handled = NULL;


static void find_entry_pt(IRSB* bb_orig, FunctionEntry *f);

// This is called whenever we encounter an IMark statement.  From the
// IR documentation (Copyright (c) 2004-2005 OpenWorks LLP):
//
// IMark(literal guest address, length)
//
// Semantically a no-op.  However, indicates that the IR statements
// which follow it originally came from a guest instruction of the
// stated length at the stated guest address.  This information is
// needed by some kinds of profiling tools.

// This function is provided with a super block (one entry, multiple
// exit) of IR instructions.

// We will utilize this information to pause the target program at
// function entrances. For further information on how Fjalar
// determines the address for function entrances please see the
// "HANDLING FUNCTION ENTRY" comment below. This is called from
// mc_translate.c.
void handle_possible_entry(MCEnv* mce, Addr64 addr, IRSB* bb_orig) {
  // REMEMBER TO ALWAYS UPDATE THIS regardless of whether this is
  // truly a function entry so that handle_possible_exit() can work
  // properly:
  currentAddr = (Addr)addr;

  if(!fjalar_gcc3) {
    FunctionEntry *entry = gengettable(FunctionTable, (void *)(Addr)addr);
    if(entry) {
      find_entry_pt(bb_orig, entry);
    }
  }

  // We're not splitting entry handling based on GCC version.
  // for GCC 3.x we're going to enter at the instruction
  // corresponding to the first line of code in a function
  // (f->entryPC in Fjalar's terms)

  // For GCC 4.x we're going to use a special heuristic for
  // determining the instruction to enter at. See comment
  // "HANDLING FUNCTION ENTRY" above find_entry_pt()
  if(fjalar_gcc3) {

    /* If this is the very first instruction in the function, add a call
       to the prime_function helper. */
    handle_possible_entry_func(mce, addr, FunctionTable,
			       "prime_function",
			       &prime_function);

    /* If this is the first instruction in the function after the prolog
       (not exclusive with the condition above), add a call to the
       enter_function helper. */
    handle_possible_entry_func(mce, addr, FunctionTable_by_entryPC,
			       "enter_function",
			       &enter_function);
  } else {
    handle_possible_entry_func(mce, addr, FunctionTable_by_endOfBb,
			       "enter_function",
			       &enter_function);
  }

}


// HANDLING FUNCTION ENTRY
// For most functions the debugging information is essentially
// useless before the prolog. This was mitigated in earlier versions
// by entering functions at the instruction corresponding to the
// first line in the source code (entryPC in Fjalar terms). This
// causes a problem in some cases when the body of a function
// consists only of a loop and the compiler decides to be off
// about presenting line information. For Example:

// (pseduo x86 assembly)
// jmp Test
// Body:
// add
// ... Body of loop
// Test:
// cmp eax ecx
// jne Test

// The issue occurs because some versions of GCC will choose to
// correlate the first line of the function with the first instruction
// after "jmp test". This makes it impossible for Fjalar to detect
// function entry for functions whose loop body is never executed.
// It also causes problems relating to detecting entry to a function
// multiple times, though this has already been mitigated - see comment
// above prime_functoin

// This causes a problem as we can't enter at the first instruction due
// to invalid debugging information, nor can we enter at the entryPC
// due to loops (and possibly any function that begins with a conditional)

// We solve this by applying the following heuristic to determine
// the entry point to a function:

// If the first basic block of a function ends before entryPC, use
// the last instruction of that basic block as our entrypoint. Otherwise
// use entryPC
static void find_entry_pt(IRSB* bb_orig, FunctionEntry *f) {
  int i;
  Addr entry_pt = 0;

  if(gencontains(funcs_handled, f))
    return;

  if (dyncomp_delayed_trace) {
    dyncomp_print_trace_info = True;
    dyncomp_delayed_trace = False;
  }

  if (dyncomp_delayed_print_IR) {
    fjalar_print_IR = True;
    dyncomp_delayed_print_IR = False;
  }

  FJALAR_DPRINTF("[find_entry_pt] Searching %s for entry address %x\n", f->fjalar_name, (UInt)f->entryPC);
  for(i=0 ; i <  bb_orig->stmts_used; i++) {
    IRStmt *st = bb_orig->stmts[i];
    if(st->tag == Ist_IMark) {
      FJALAR_DPRINTF("\tEncountered IMark for address %x\n", (UInt)st->Ist.IMark.addr);
      if(st->Ist.IMark.addr <= f->entryPC) {
	entry_pt = st->Ist.IMark.addr;
      }
    }
  }
  tl_assert( entry_pt );

  FJALAR_DPRINTF("\t%x chosen for entry\n", (UInt)entry_pt);

  genputtable(funcs_handled, (void *)f, (void *)1);

  genputtable(FunctionTable_by_endOfBb,
	      (void *)entry_pt,
	      (void *)f);

}


// Handle a function exit statement, which contains a jump kind of
// 'Ret'.  It seems pretty accurate to cue off of currentAddr, a value
// that is updated every time an Ist_IMark statement is translated,
// which is quite often
void handle_possible_exit(MCEnv* mce, IRJumpKind jk) {
  if (Ijk_Ret == jk) {
    IRDirty  *di;

    FunctionEntry* curFuncPtr = getFunctionEntryFromAddr(currentAddr);

    if (curFuncPtr &&
	// Also, if fjalar_trace_prog_pts_filename is on (we are
	// reading in a ppt list file), then DO NOT generate IR code
	// to call helper functions for functions whose names are NOT
	// located in prog_pts_tree.  This will greatly speed up
	// processing because these functions are filtered out at
	// translation-time, not at run-time
	(!fjalar_trace_prog_pts_filename ||
	 prog_pts_tree_entry_found(curFuncPtr))) {

      FJALAR_DPRINTF("[handle_possible_exit] %s - %x\n", curFuncPtr->fjalar_name, (UInt)currentAddr);

      // The only argument to exit_function() is a pointer to the
      // FunctionEntry for the function that we are exiting
      di = unsafeIRDirty_0_N(1/*regparms*/,
			     "exit_function",
			     &exit_function,
			     mkIRExprVec_1(IRExpr_Const(IRConst_UWord((Addr)curFuncPtr))));

      // For function exit, we are interested in observing  all general purpose
      // integer registers,  FTOP, and FPREG[], so make sure that they are
      // updated by setting the proper annotations.
      di->nFxState = 11;
      vex_bzero(&di->fxState, sizeof(di->fxState));

      di->fxState[0].fx     = Ifx_Read;
      di->fxState[0].offset = mce->layout->offset_SP;
      di->fxState[0].size   = mce->layout->sizeof_SP;
      di->fxState[1].fx     = Ifx_Read;
      di->fxState[1].offset = mce->layout->offset_FP;
      di->fxState[1].size   = mce->layout->sizeof_FP;
      di->fxState[2].fx     = Ifx_Read;
      di->fxState[2].offset = mce->layout->offset_IP;
      di->fxState[2].size   = mce->layout->sizeof_IP;

      di->fxState[3].fx     = Ifx_Read;
      di->fxState[3].offset = mce->layout->offset_xAX;
      di->fxState[3].size   = mce->layout->sizeof_xAX;
      di->fxState[4].fx     = Ifx_Read;
      di->fxState[4].offset = mce->layout->offset_xBX;
      di->fxState[4].size   = mce->layout->sizeof_xBX;
      di->fxState[5].fx     = Ifx_Read;
      di->fxState[5].offset = mce->layout->offset_xCX;
      di->fxState[5].size   = mce->layout->sizeof_xCX;

      di->fxState[6].fx     = Ifx_Read;
      di->fxState[6].offset = mce->layout->offset_xDX;
      di->fxState[6].size   = mce->layout->sizeof_xDX;
      di->fxState[7].fx     = Ifx_Read;
      di->fxState[7].offset = mce->layout->offset_xSI;
      di->fxState[7].size   = mce->layout->sizeof_xSI;
      di->fxState[8].fx     = Ifx_Read;
      di->fxState[8].offset = mce->layout->offset_xDI;
      di->fxState[8].size   = mce->layout->sizeof_xDI;

      di->fxState[9].fx     = Ifx_Read;
      di->fxState[9].offset = offsetof(VexGuestArchState, guest_FTOP);
      di->fxState[9].size   = sizeof(UInt); /* FTOP is 4 bytes even on x64 */
      di->fxState[10].fx     = Ifx_Read;
      di->fxState[10].offset = offsetof(VexGuestArchState, guest_FPREG);
      di->fxState[10].size   = 8 * sizeof(ULong);

      stmt('V',  mce, IRStmt_Dirty(di) );
    }
  }
}

/* A disadvantage of putting the call to enter_function after the
   prolog is that it occasionally ends up at a label that the compiler
   jumps back to in the middle of executing a function, say if the
   whole function is a single loop. If we were to do all the stuff in
   enter_function() again in this case, things would get very
   confused. Instead, we want to only do enter_function() once per
   invocation of the function, where we define an invocation to be an
   execution of the very first instruction. To accomplish that, we put
   a call to the prime_function() hook there; it initializes a global
   to point to the current function. In enter_function(), we check
   that pointer before doing anything, and then clear it. */
static FunctionEntry* primed_function = 0;
VG_REGPARM(1) void prime_function(FunctionEntry *f)
{
  primed_function = f;
  return;
}


static UInt cur_nonce = 0;
/*
This is the hook into Valgrind that is called whenever the target
program enters a function.  Pushes an entry onto the top of
FunctionExecutionStateStack and calls out to a handler function
implemented by the Fjalar tool.
*/
VG_REGPARM(1)
void enter_function(FunctionEntry* f)
{
  FunctionExecutionState* newEntry;
  extern FunctionExecutionState* curFunctionExecutionStatePtr;

  ThreadId tid = VG_(get_running_tid)();
  Addr stack_ptr= VG_(get_SP)(tid);
  Addr frame_ptr = 0; /* E.g., %ebp */
  int local_stack, size;

  FJALAR_DPRINTF("[enter_function] startPC is: %x, entryPC is: %x, cu_base: %p\n",
                 (UInt)f->startPC, (UInt)f->entryPC,(void *)f->cuBase);
  FJALAR_DPRINTF("Value of edi: %lx, esi: %lx, edx: %lx, ecx: %lx\n",
      (long)VG_(get_xDI)(tid), (long)VG_(get_xSI)(tid), (long)VG_(get_xDX)(tid), (long)VG_(get_xCX)(tid));

  // Determine the frame pointer for this function using DWARF
  // location lists. This is a "virtual frame pointer" in that it is
  // used by the DWARF debugging information in providing the address
  // of formal parameters and local variables, but it may or may not
  // correspond to an actual frame pointer in the architecture. For
  // example: This will not always return %xbp on x86{-64} platforms
  // and *SHOULD*(untested) work with the -fomit-frame-pointer flag in GCC
  //
  // It usually points just above the function return address.  The
  // .debug_loc info tells how to find (calculate) the frame base
  // at any point in the program.   (markro)
  if(f->locList) {
    Addr eip = f->entryPC;
    location_list *ll;
    eip =  eip - f->cuBase;

    FJALAR_DPRINTF("\tCurrent EIP is: %x\n", (UInt)eip);
    FJALAR_DPRINTF("\tLocation list based function(offset from base: %x). offset is %lu\n",(UInt)eip, f->locListOffset);

    if (gencontains(loc_list_map, (void *)f->locListOffset)) {
      ll = gengettable(loc_list_map, (void *)f->locListOffset);

      // (comment added 2009)  
      // HACK. g++ and GCC handle location lists differently. GCC puts lists offsets
      // relative to the compilation unit, g++ uses the actual address. I'm going to
      // compare the location list ranges both to the cu_base offset, as well as
      // the function's entry point. This might break if there's every a case
      // where the compilation unit offset is a valid address in the program
      while(ll &&
            !(((ll->begin <= eip) && (ll->end >= eip)) ||
              ((ll->begin <= f->entryPC) && (ll->end >= f->entryPC)))) {
        FJALAR_DPRINTF("\tExamining loc list entry: %x - %x - %x\n", (UInt)ll->offset, (UInt)ll->begin, (UInt)ll->end);
        ll = ll->next;
      }

      if(ll) {
        FJALAR_DPRINTF("\tFound location list entry, finding location corresponding to dwarf #: %d with offset: %lld\n", ll->atom, ll->atom_offset);

        // (comment added 2013)  
        // It turns out it might not be just the contents of a register.  Some
        // 32bit x86 code does some tricky stack alignment and has to save a
        // pointer to the orginal stack frame.  This means we get passed a 
        // DW_OP_deref instead of a DW_OP_breg.  The tricky bit is we don't
        // want to go back to that address because it probably won't be equal
        // to the local frame pointer due to the stack alignment.  So the HACK
        // is to just assume the frame pointer is at EBP+8 like normal.  (markro)
        if (ll->atom == DW_OP_deref) {
            ll->atom = DW_OP_breg5;
            ll->atom_offset = 8;
        }    
        if(get_reg[ll->atom - DW_OP_breg0]) {
          frame_ptr = (*get_reg[ll->atom - DW_OP_breg0])(tid) + ll->atom_offset;
        }
      }
    }
  }


  // This is the old code to determine the frame. Fallback to it if we don't
  // have a frame_base from the location_list path. This should keep GCC 3 working
  // fine.
  if(frame_ptr == 0) {
    if (f != primed_function) {
      printf("No location list or frame pointer giving up(Mangled name: %s)\n", f->mangled_name);
      return;
    }
    primed_function = 0;

    if (f->entryPC != f->startPC) {
      /* Prolog has run, so just use the real %ebp */
      frame_ptr = VG_(get_FP)(VG_(get_running_tid)());
    } else {
      FJALAR_DPRINTF("Faking prolog\n");
      /* Don't know about prolog, so fake its effects, given we know that
         ESP hasn't yet been modified: */
      // Looks like we never get here for amd64 as -4 is clearly wrong. (10/26/2015)
      frame_ptr = stack_ptr - 4;
    }
  }

  FJALAR_DPRINTF("\tEnter function: %s - StartPC: %p, EntryPC: %p, frame_ptr: %p\n",
		 f->fjalar_name, (void *)f->startPC, (void *)f->entryPC, (void *)frame_ptr);

  newEntry  = fnStackPush(tid);
  newEntry->func = f;
  newEntry->func->FP = frame_ptr;
  newEntry->func->lowestSP = stack_ptr;
  newEntry->FP = frame_ptr;
  newEntry->lowSP = stack_ptr;
  newEntry->lowestSP = stack_ptr;
  newEntry->xAX = 0;
  newEntry->xDX = 0;
  newEntry->FPU = 0;
  newEntry->invocation_nonce = cur_nonce++;
  newEntry->func->nonce = newEntry->invocation_nonce;

  // FJALAR VIRTUAL STACK
  // Fjalar maintains a virtual stack for invocation a function. This
  // allows Fjalar to provide tools with unaltered values of formal
  // parameters at both function entry and exit, regardless of whether
  // or not the compiler chooses to use the original formal parameter
  // locations as storage for local values.

  // Initialize virtual stack and copy parts of the Valgrind stack
  // into that virtual stack
  local_stack = frame_ptr - stack_ptr + VG_STACK_REDZONE_SZB; /* in our frame */
  tl_assert(local_stack >= 0);
  FJALAR_DPRINTF("frame_ptr: %p, stack_ptr: %p, VG_STACK_REDZONE: %d\n", (void *)frame_ptr, (void *)stack_ptr, VG_STACK_REDZONE_SZB);

  // The virtual stack consists of:
  // (1) local_stack: the entirety of the function's local stack (the
  // memory between the frame pointer and the stack pointer (including the extra
  // redzone)
  // (2) The return pointer, which is sizeof(Addr) bytes
  // (3) The saved base pointer, which is sizeof(Addr) bytes
  // (4) All formal parameters passed on the stack, which is
  //     f->formalParamStackByteSize bytes

  // Let's be conservative in how much we copy over to the Virtual stack. Due to the
  // stack alignment operations in main, we may need  as much as 16 bytes over the above.
  size = local_stack + f->formalParamStackByteSize + sizeof(Addr)*2 + 32;/* plus stuff in caller's*/
  FJALAR_DPRINTF("local_stack: %p, arg_size: %d\n", (void *)(frame_ptr - f->formalParamLowerStackByteSize),
                                                    f->formalParamLowerStackByteSize);
  int delta = stack_ptr - (frame_ptr - f->formalParamLowerStackByteSize);
  if (delta < 0 )
      delta = 0;

  tl_assert(size >= 0);
  if (size != 0) {
    newEntry->virtualStack = VG_(calloc)("fjalar_main.c: enter_func",  size, sizeof(char));
    newEntry->virtualStackByteSize = size;
    newEntry->virtualStackFPOffset = local_stack;

    clear_all_tags_in_range(stack_ptr - VG_STACK_REDZONE_SZB, VG_STACK_REDZONE_SZB - delta);

    VG_(memcpy)(newEntry->virtualStack,
		(char*)stack_ptr - VG_STACK_REDZONE_SZB, size);

    // VERY IMPORTANT!!! Copy all the A & V bits over the real stack to
    // virtualStack!!!  (As a consequence, this copies over the tags
    // as well - look in mc_main.c). Note that the way do this means
    // that the copy is now guest-accessible, if they guessed the
    // VG_(calloc)ed address, which is a bit weird. It would be more
    // elegant to copy the metadata to an inaccessible place, but that
    // would be more work.
    FJALAR_DPRINTF("Copying over stack [%p] -> [%p] %d bytes\n",(void *)(stack_ptr - VG_STACK_REDZONE_SZB),  (void *)newEntry->virtualStack, size);
    mc_copy_address_range_state(stack_ptr - VG_STACK_REDZONE_SZB,
				(Addr)(newEntry->virtualStack), size);


    newEntry->func->guestStackStart = stack_ptr - VG_STACK_REDZONE_SZB;
    newEntry->func->guestStackEnd = newEntry->func->guestStackStart + size;
    newEntry->func->lowestVirtSP = (Addr)newEntry->virtualStack;

  }
  else {
    printf("Obtained a stack size of 0 for Function: %s. Aborting\n", f->fjalar_name);
    tl_assert(0);
  }


  // Do this AFTER initializing virtual stack and lowestSP
  curFunctionExecutionStatePtr = newEntry;
  fjalar_tool_handle_function_entrance(newEntry);
}

/*
This is the hook into Valgrind that is called whenever the target
program exits a function.  Initializes the top entry of
FunctionExecutionStateStack with return values from EAX, EDX, and FPU,
then calls out to a handler function implemented by the Fjalar tool.
*/
VG_REGPARM(1)
void exit_function(FunctionEntry* f)
{
  ThreadId currentTID = VG_(get_running_tid)();
  FunctionExecutionState* top = fnStackTop(currentTID);
  extern FunctionExecutionState* curFunctionExecutionStatePtr;
  int i;
  ULong FPUshadow;
  double fpuReturnVal;
  Addr xAX, xDX, xAXshadow, xDXshadow;
  Bool foundFunc;

  FJALAR_DPRINTF("Exit function: %s\n", f->fjalar_name);

  top->func->guestStackStart = top->lowSP - VG_STACK_REDZONE_SZB;
  top->func->guestStackEnd = top->func->guestStackStart + top->virtualStackByteSize;
  top->func->lowestVirtSP = (Addr)top->virtualStack;
  top->func->FP  = top->FP;
  top->func->lowestSP  = top->func->guestStackStart;

  FJALAR_DPRINTF("\tState of Guest Stack [%p - %p] \n", (void *)top->lowestSP, (void *)(top->lowestSP + top->virtualStackByteSize));

  // Ok, in Valgrind 2.X, we needed to directly code some assembly to
  // grab the top of the floating-point stack, but Valgrind 3.0
  // provides a virtual FPU stack, so we can just grab that.  Plus, we
  // now have shadow V-bits for the FPU stack.

#if defined(VGA_amd64)
  // XMM registers are represented as a 128-bit integer
  // (Actually an array of 4 32-bit integers), so reinterpret
  // cast it as a double.
  FPUshadow = (VG_(get_shadow_XMM_N)(currentTID, 0))[0];
  fpuReturnVal = *(double *)VG_(get_XMM_N)(currentTID, 0);
  //RUDD DEBUG
  /* for(i=0 ; i < 4; i++) { */
  /*   printf("Testing %d\n", test[i]); */
  /*   printf("shadow: %x\n", testing[i]); */
  /* }    */

#else
  fpuReturnVal = VG_(get_FPU_stack_top)(currentTID);
  FPUshadow = VG_(get_shadow_FPU_stack_top)(currentTID);
#endif


  //RUDD DEBUG
  /* printf("%.16g\n", fpuReturnVal); */
  /* printf("shadow: %x\n", FPUshadow); */
  // Get the value at the simulated %EAX (integer and pointer return
  // values are stored here upon function exit)
  xAX = VG_(get_xAX)(currentTID);

  // Get the value of the simulated %EDX (the high 32-bits of the long
  // long int return value is stored here upon function exit)
  xDX = VG_(get_xDX)(currentTID);


  // 64 bits
  // Use SHADOW values of Valgrind simulated registers to get V-bits
  xAXshadow = VG_(get_shadow_xAX)(currentTID);
  xDXshadow = VG_(get_shadow_xDX)(currentTID);

  FJALAR_DPRINTF("Value of eax: %x, edx: %x\n",(int)xAX, (int)xDX);

  FJALAR_DPRINTF("Exit function: %s\n", f->fjalar_name);

  // Only do something if top->func matches func
  if (!top->func) {
    printf("More exit_function()s than entry_function()s!\n");
    // RUDD EXCEPTION
    VG_(get_and_pp_StackTrace) (currentTID, 15);
    return;
  } else if (!(top->func->fjalar_name) || (top->func != f)) {
    // There are a couple reasons why the function at the top
    // of the Function Execution State Stack would not be the
    // function we expected. All of them are related to a non-
    // local exit of the function. Situations where this might
    // come up include:

    // (1) C++ Exceptions
    // (2) setjmp/longjmp

    // For Fjalar to resume normal operation, we need to pop
    // off functions off the Function Execution State Stack
    // (these would be all the functions that had non-local
    // exits) until we encounter the Function Execution State
    // Stack corresponding to our function.
    printf("MISMATCHED on exit_function! f: %s !=  %s\nDetectedEntryIP: %p - AssumedEntryIP: %p\nDetctedExitIP: %p - AssumedExitIp: %p\n",
                f->fjalar_name,
                top->func->fjalar_name,
                (void *)top->func->entryPC,
                (void *)f->entryPC,
                (void *)top->func->endPC,
                (void *)f->endPC);


    // This is probably being overconservative. However let's revert
    // to Fjalar's old behavior (do nothing) if we can't find an
    // instance of our function in the function stack.
    for(i = fn_stack_first_free_index[currentTID] - 1; i >= 0; i-- ) {
      FunctionExecutionState* curFuncExecPtr = &FunctionExecutionStateStack[currentTID][i];
      if(curFuncExecPtr->func == f) {
        foundFunc = True;
        break;
      }
    }

    if(!foundFunc) {
      VG_(get_and_pp_StackTrace) (currentTID, 15);
      return;
    }

    while(top->func) {
      top = fnStackTop(currentTID);
      if(top->func == f) {
        break;
      }
      fnStackPop(currentTID);
    }

    tl_assert(top->func == f);
  }

  top->xAX = xAX;
  top->xDX = xDX;
  top->FPU = fpuReturnVal;

  // Very important!  Set the A and V bits of the appropriate
  // FunctionExecutionState object and the tags from the (x86) guest
  // state as well:
  for (i = 0; i < sizeof(Addr); i++) {
    set_abit_and_vbyte((Addr)(&top->xAX) + (Addr)i, VGM_BIT_VALID,
                      (xAXshadow & 0xff) << (i * 8));
    set_abit_and_vbyte((Addr)(&top->xDX) + (Addr)i, VGM_BIT_VALID,
                      (xDXshadow & 0xff) << (i * 8));
    set_abit_and_vbyte((Addr)(&top->FPU) + (Addr)i, VGM_BIT_VALID,
                      (FPUshadow & 0xff) << (i * 8));
  }

  for (i = 0; i < 8; i++) {
    set_abit_and_vbyte((Addr)(&top->FPU) + (Addr)i, VGM_BIT_VALID,
                       (FPUshadow & 0xff) << (i * 8));
  }

  curFunctionExecutionStatePtr = top;
  top->func->nonce = top->invocation_nonce;

  fjalar_tool_handle_function_exit(top);

  // Destroy the memory allocated by virtualStack
  // AFTER the tool has handled the exit
  if (top->virtualStack) {
    /* We were previously using the V bits associated with the area to
       store guest V bits, but Memcheck doesn't normally expect
       VG_(malloc)'ed memory to be client accessible, so we have to
       make it inaccessible again before allowing Valgrind's malloc to
       use it, lest assertions fail later. */
    mc_make_noaccess((Addr)top->virtualStack, top->virtualStackByteSize);
    VG_(free)(top->virtualStack);
  }

  // Pop at the VERY end after the tool is done handling the exit.
  // This is subtle but important - this must be done AFTER the tool
  // runs all of it's function exit code, as functions in fjalar_traversal
  // and fjalar_runtime may make use of the function stack. If we fail to
  // pop the function, however, the stack will be left in an inconsistant
  // state and the "!top->func == f" check will fail causing no more
  // program points to be printed.
  fnStackPop(currentTID);

}


/*------------------------------------------------------------*/
/*--- Command line processing                              ---*/
/*------------------------------------------------------------*/

// Opens the appropriate files and loads data to handle selective
// program point tracing, selective variable tracing, and pointer type
// disambiguation.  Call this before initializeAllFjalarData() because
// it might depend on the vars_tree being initialized.
// Handles the following command-line options:
//   --ppt-list-file
//   --var-list-file
static void loadAuxiliaryFileData(void) {

  if (fjalar_trace_prog_pts_filename) {
    if ((trace_prog_pts_input_fp =
	 fopen(fjalar_trace_prog_pts_filename, "r"))) {
      printf( "\nBegin processing program point list file \"%s\" ...\n",
		   fjalar_trace_prog_pts_filename);
      initializeProgramPointsTree();
      printf( "Done processing program point list file \"%s\"\n",
		   fjalar_trace_prog_pts_filename);
    }
    else {
      printf( "\nError: \"%s\" is an invalid filename for the program point list file specified by the --ppt-list-file option.\n\nExiting.\n\n",
		   fjalar_trace_prog_pts_filename);

      VG_(exit)(1);
    }
  }

  if (fjalar_trace_vars_filename) {
    if ((trace_vars_input_fp
	 = fopen(fjalar_trace_vars_filename, "r"))) {
      printf( "\nBegin processing variable list file \"%s\" ...\n",
		   fjalar_trace_vars_filename);
      initializeVarsTree();
      printf( "Done processing variable list file \"%s\"\n",
		   fjalar_trace_vars_filename);
    }
    else {
      printf( "\nError: \"%s\" is an invalid filename for the variable list file specified by the --var-list-file option.\n\nExiting.\n\n",
		   fjalar_trace_vars_filename);

      VG_(exit)(1);
    }
  }
}


// If we want to dump program point list, variable list, or XML to
// output files, do it here, close the appropriate files, and then
// exit (notice that this supports writing to more than 1 kind of file
// before exiting).  We want to do this after
// initializeAllFjalarData() so that all of the data from
// generate_fjalar_entries.h will be available.
// This function has no effect if we are not using any of the options
// to output auxiliary files.
// Handles the following command-line options:
//   --dump-ppt-file
//   --dump-var-file
//   --xml-output-file
static void outputAuxiliaryFilesAndExit(void) {
  if (fjalar_dump_prog_pt_names_filename ||
      fjalar_dump_var_names_filename ||
      fjalar_xml_output_filename) {
    if (fjalar_dump_prog_pt_names_filename) {
      prog_pt_dump_fp = fopen(fjalar_dump_prog_pt_names_filename, "w");
      tl_assert(prog_pt_dump_fp);
      outputProgramPointsToFile();
      printf("\nDone generating program point list (ppt-list) file %s\n",
                  fjalar_dump_prog_pt_names_filename);
      fclose(prog_pt_dump_fp);
      prog_pt_dump_fp = 0;
    }

    if (fjalar_dump_var_names_filename) {
      var_dump_fp = fopen(fjalar_dump_var_names_filename, "w");
      tl_assert(var_dump_fp);
      outputVariableNamesToFile();
      printf("\nDone generating variable list (var-list) file %s\n",
                  fjalar_dump_var_names_filename);
      fclose(var_dump_fp);
      var_dump_fp = 0;
    }

    // Output the declarations in XML format if desired, and then exit:
    if (fjalar_xml_output_filename) {
      xml_output_fp = fopen(fjalar_xml_output_filename, "w");
      outputAllXMLDeclarations();
      printf("\nDone generating XML file %s\n",
                  fjalar_xml_output_filename);
      fclose(xml_output_fp);
      xml_output_fp = 0;
    }

    VG_(exit)(0);
  }
}


// This is called before command-line options are processed
void fjalar_pre_clo_init()
{
   fn_stack_first_free_index = VG_(malloc)("fjalar_main.c: fjalar_pre_clo_init1", VG_N_THREADS * sizeof fn_stack_first_free_index[0]);
   FunctionExecutionStateStack = VG_(malloc)("fjalar_main.c: fjalar_pre_clo_init2", VG_N_THREADS * FN_STACK_SIZE * sizeof FunctionExecutionStateStack[0][0]);

  // Clear FunctionExecutionStateStack
/*   VG_(memset)(FunctionExecutionStateStack, 0, */
/* 	      FN_STACK_SIZE * sizeof(*FunctionExecutionStateStack)); */

  // (comment added 2005)  
  // TODO: Do we need to clear all global variables before processing
  // command-line options?  We don't need to as long as this function
  // is only run once at the beginning of program execution.

  // Make sure to execute this last!
  fjalar_tool_pre_clo_init();
}

// Initialize Fjalar after command-line options are processed
void fjalar_post_clo_init()
{
  const char* DISAMBIG = ".disambig";
  int DISAMBIG_LEN = VG_(strlen)(DISAMBIG);

  // We need to turn off some VEX IR optimizations (primarily the one which
  // causes separate basic blocks to be stitched together) for the purpose of
  // detecting entry in main. see "HANDLING FUNCTION ENTRY" in find_entry_pt()
  VG_(clo_vex_control).iropt_unroll_thresh = 0;
  VG_(clo_vex_control).guest_chase_thresh = 0;

  executable_filename = VG_(args_the_exename);

  if (fjalar_with_gdb) {
    int x = 0;
    while (!x) {} /* In GDB, say "p x=1" and then "c" to continue */
  }


  funcs_handled= genallocatehashtable(0,(int (*)(void *,void *)) &equivalentIDs);

  // Handle variables set by command-line options:
  // Assumes that filename is first argument in client_argv
  FJALAR_DPRINTF("\nReading binary file \"%s\" [0x%p]\n\n",
	  executable_filename, executable_filename);

  // --disambig results in the disambig filename being ${executable_filename}.disambig
  // (overrides --disambig-file option)
  if (fjalar_default_disambig) {
    char* disambig_filename =
      VG_(calloc)("fjalar_main.c: fj_po_clo_init", VG_(strlen)(executable_filename) + DISAMBIG_LEN + 1,
	     sizeof(*disambig_filename));

    VG_(strcpy)(disambig_filename, executable_filename);
    VG_(strcat)(disambig_filename, DISAMBIG);
    fjalar_disambig_filename = disambig_filename;
  }

  // There is a bug in my_libc.c that keeps printf and
  // putchar from intermixing properly.  Using NOBUF
  // on stdout keeps putchar from buffering incorrectly.
  setNOBUF(stdout);

  FJALAR_DPRINTF("\n%s\n\n", fjalar_disambig_filename);

  // Calls into typedata.c:
  initialize_typedata_structures();

  FJALAR_DPRINTF("Typedata structures completed\n");

  // Calls into readelf.c:
  process_elf_binary_data(executable_filename);

  FJALAR_DPRINTF("Process elf binary completed\n");
  // Call this BEFORE initializeAllFjalarData() so that the vars_tree
  // objects can be initialized for the --var-list-file option:
  loadAuxiliaryFileData();

  // Calls into generate_fjalar_entries.c:
  initializeAllFjalarData();
  FJALAR_DPRINTF("Fjalar data initialized\n");
  if (fjalar_disambig_filename) {
    handleDisambigFile();
  }

  // Call this AFTER initializeAllFjalarData() so that all of the
  // proper data is ready:
  outputAuxiliaryFilesAndExit();

  FJALAR_DPRINTF("Files output\n");
  // Make sure to execute this last!
  fjalar_tool_post_clo_init();
  FJALAR_DPRINTF("Tool clo initialized\n");
}


// Prints the help message when Fjalar is invoked with the --help option
void fjalar_print_usage()
{
   printf("\n  User options for Fjalar framework:\n");

   printf(
"\n  Selective program point and variable tracing:\n"
"    --ppt-list-file=<string> Trace only the program points listed in this file\n"
"    --var-list-file=<string> Trace only the variables listed in this file\n"
"    --dump-ppt-file=<string> Outputs all program point names to a file\n"
"    --dump-var-file=<string> Outputs all variable names to a file\n"
"    --ignore-globals         Ignores all global variables [--no-ignore-globals]\n"
"    --ignore-static-vars     Ignores all static variables [--no-ignore-static-vars]\n"
"    --ignore-constants       Ignores all constant variables [--no-ignore-constants]\n"
"    --all-static-vars        Output all static vars [--no-all-static-vars]\n"

"\n  Pointer type disambiguation:\n"
"    --disambig-file=<string> Reads in disambig file if exists; otherwise creates one\n"
"    --disambig               Uses <program name>.disambig as the disambig file\n"
"    --smart-disambig         Infers sensible values for each entry in .disambig file\n"
"                             generated using the --disambig or --disambig-file options\n"
"    --func-disambig-ptrs     Treats function parameter and return value pointer\n"
"                             variables as pointing to a single element\n"
"    --disambig-ptrs          Treats all pointer vars. as pointing to a single element\n"

"\n  Misc. options:\n"
"    --flatten-arrays         Force flattening of all statically-sized arrays\n"
"    --array-length-limit=N   Only visit at most the first N elements of arrays\n"
"    --nesting-depth=N        Limits the maximum number of dereferences of any\n"
"                             structure to N (default is 2)\n"
"    --struct-depth=N         Limits the maximum number of dereferences of recursively\n"
"                             defined structures (i.e. linked lists) to N (default is 4)\n"
"                             (N must be an integer between 0 and 100)\n"
"    --output-struct-vars     Outputs struct variables along with their contents\n"

"\n  Debugging:\n"
"    --xml-output-file=<string>  Output declarations in XML format to a file\n"
"    --with-gdb               Hang during init. so that GDB can attach to it\n"
"    --fjalar-debug           Print internal Fjalar debug messages\n"
"    --fjalar-debug-dump      Mimic /usr/bin/readelf --debug_dump\n"
"    --fjalar-print-dwarf     Print internal dwarf entry table (reguires --fjalar-debug\n"
"    --fjalar-print-ir        Print Intermediate Representation trees (reguires --fjalar-debug)\n"
   );
   // Make sure to execute this last!
   fjalar_tool_print_usage();
}


// Processes command-line options and sets the values of the
// appropriate global variables (Called from
// MAC_(process_common_cmd_line_option)() in mac_shared.c)
Bool fjalar_process_cmd_line_option(const HChar* arg)
{

  if VG_YESNO_CLO(arg, "fjalar-debug", fjalar_debug) {}
  else if VG_YESNO_CLO(arg, "fjalar-debug-dump", fjalar_debug_dump) {}
  else if VG_YESNO_CLO(arg, "fjalar-print-dwarf", fjalar_print_dwarf) {}
  else if VG_YESNO_CLO(arg, "fjalar-print-ir", fjalar_print_IR) {}
  else if VG_YESNO_CLO(arg, "with-gdb", fjalar_with_gdb) {}
  else if VG_YESNO_CLO(arg, "ignore-globals", fjalar_ignore_globals) {}
  else if VG_YESNO_CLO(arg, "dump-globals", fjalar_dump_globals) {}
  else if VG_YESNO_CLO(arg, "ignore-constants", fjalar_ignore_constants) {}
  else if VG_YESNO_CLO(arg, "merge-constants", fjalar_merge_constants) {}
  else if VG_YESNO_CLO(arg, "ignore-static-vars", fjalar_ignore_static_vars) {}
  else if VG_YESNO_CLO(arg, "all-static-vars", fjalar_all_static_vars) {}
  else if VG_YESNO_CLO(arg, "gcc3", fjalar_gcc3) {}
  else if VG_YESNO_CLO(arg, "disambig", fjalar_default_disambig) {}
  else if VG_YESNO_CLO(arg, "smart-disambig", fjalar_smart_disambig) {}
  else if VG_YESNO_CLO(arg, "output-struct-vars", fjalar_output_struct_vars) {}
  else if VG_YESNO_CLO(arg, "flatten-arrays", fjalar_flatten_arrays) {}
  else if VG_YESNO_CLO(arg, "func-disambig-ptrs", fjalar_func_disambig_ptrs) {}
  else if VG_YESNO_CLO(arg, "disambig-ptrs", fjalar_disambig_ptrs) {}
  else if VG_BINT_CLO(arg, "--array-length-limit", fjalar_array_length_limit,
		      -1, 0x7fffffff) {}

  /* else if VG_BINT_CLO(arg, "--struct-depth",  fjalar_max_visit_struct_depth, 0, 100)  {} // [0 to 100]
     else if VG_BINT_CLO(arg, "--nesting-depth", fjalar_max_visit_nesting_depth, 0, 100) {} // [0 to 100] */
  else if VG_INT_CLO(arg, "--struct-depth",  fjalar_max_visit_struct_depth) {}
  else if VG_INT_CLO(arg, "--nesting-depth", fjalar_max_visit_nesting_depth) {}

  else if VG_STR_CLO(arg, "--dump-ppt-file",
		     fjalar_dump_prog_pt_names_filename) {}
  else if VG_STR_CLO(arg, "--dump-var-file",  fjalar_dump_var_names_filename){}
  else if VG_STR_CLO(arg, "--ppt-list-file",  fjalar_trace_prog_pts_filename){}
  else if VG_STR_CLO(arg, "--var-list-file",  fjalar_trace_vars_filename) {}
  else if VG_STR_CLO(arg, "--disambig-file",  fjalar_disambig_filename) {}
  else if VG_STR_CLO(arg, "--xml-output-file", fjalar_xml_output_filename) {}
  else
    return fjalar_tool_process_cmd_line_option(arg);

  return True;
}


// This runs after the target program exits
void fjalar_finish(void) {

  // If fjalar_smart_disambig is on, then
  // we must create the .disambig file at the very end after
  // Fjalar has run though the entire program so that it can
  // determine whether each pointer variable has only referenced
  // one element or multiple elements throughout this particular execution
  if (disambig_writing && fjalar_smart_disambig) {
    generateDisambigFile();
    printf("\nDone generating .disambig file %s\n",
                fjalar_disambig_filename);
    fclose(disambig_fp);
    disambig_fp = 0;
  }

  // Make sure to execute this last!
  fjalar_tool_finish();
}
